package arithmetic.LeetCode;

/**
 * @author jiangfeng 2019/7/26 22:05
 */
public class Alibaba {

    public static void main(String[] args) {
        int a[]={5,3,4,6,2,10,12,1};
        //int a[] = {3,9};
        //changeArr(a,1);
        //changeArr(a,7);
        //System.out.println(JsonOutput.toJson(a));
        //
        int a2[]={5,3,4,6,1,2,10,12,1,15};

       // int[] a1={5,3,4,6,2,10,12,1};

        System.out.println(maxProfit_k_1(a2));

    }

    public static void changeArr(int[] a,int i){
       swap(a,0,a.length-1);
       swap(a,0,a.length-i-2);
       swap(a,a.length-i,a.length-1);
    }

    public static void swap(int[] a,int i,int j){
        while (i<j){
            int temp=a[i];
            a[i++]=a[j];
            a[j--]=temp;
        }
    }

    /**
     * 2.股票最佳买卖时机
     */
    public static int buyTickets(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;

        //作者：LeetCode
        // 链接：https://leetcode-cn.com/problems/two-sum/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode/
        // 来源：力扣（LeetCode）
        // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    }

    /**
     * base case：
     * dp[-1][k][0] = dp[i][0][0] = 0
     * dp[-1][k][1] = dp[i][0][1] = -infinity
     *
     * 状态转移方程：
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     *
     * @param prices
     * @return
     */
    public  static int maxProfit_k_1(int[] prices) {
        int n = prices.length;
        // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
        int dp0 = 0, dp1 = Integer.MIN_VALUE;
        int buy=0,sell=0,tempChange=0;
        for (int i = 0; i < n; i++) {
            // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            //dp0 = Math.max(dp0, dp1 + prices[i]);
            if (dp0 < dp1 + prices[i]) {
                dp0 = dp1 + prices[i];
                sell = i;//记录卖的那天
                buy = tempChange;//离卖的那天最近的买的一天
            }
            if (dp1 < -prices[i]) {
                dp1 = -prices[i];
                tempChange=i;
            }
            // dp[i][1] = max(dp[i-1][1], -prices[i])
            // dp1 = Math.max(dp1, -prices[i]);
        }
        System.out.println(buy);
        System.out.println(sell);
        return dp0;
    }

    //链接：https://leetcode-cn.com/problems/two-sum/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/


    // 返回最大利润
    public  static int maxProfit(int[] prices) {
        int n = prices.length;
        int dp0 = 0, dp1 = Integer.MIN_VALUE;
        int buy=0,sell=0,tempChange=0;
        for (int i = 0; i < n; i++) {
            if (dp0 < dp1 + prices[i]) {
                dp0 = dp1 + prices[i];
                sell = i;//记录卖的那天
                buy = tempChange;//离卖的那天最近的买的一天
            }
            if (dp1 < -prices[i]) {
                dp1 = -prices[i];
                tempChange=i;
            }
        }
        System.out.println(buy);
        System.out.println(sell);
        return dp0;
    }

}
